'''
https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/description/
'''


def f(s):
    num = ['1' if c == '0' else '0' for c in s]
    num = num[::-1]
    tail = ''.join(num)
    return s + '1' + tail
s = '0'
for _ in range(19):
    s = f(s)

class Solution:
    def findKthBit2(self, n: int, k: int) -> str:
        return s[k-1]

    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return '0'
        len = (1 << n) - 1
        mid = len // 2 + 1      # 1~k
        if k == mid:
            return '1'
        elif k < mid:
            return self.findKthBit(n - 1, k)
        else:
            # len=5, k=4        查找第2个
            # len=11, k=7        查找第5个
            k = len-k+1
            return '0' if self.findKthBit(n - 1, k) == '1' else '1'



n = 18
k = 189470
print(Solution().findKthBit(n, k))